// 版权归Go作者所有。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// go:构建aix |达尔文|蜻蜓| freebsd | linux | netbsd | openbsd | solaris 

// 最小RFC 6724地址选择。

package net

import "sort"

func sortByRFC6724(addrs []IPAddr) {
	if len(addrs) < 2 {
		return
	}
	sortByRFC6724withSrcs(addrs, srcAddrs(addrs))
}

func sortByRFC6724withSrcs(addrs []IPAddr, srcs []IP) {
	if len(addrs) != len(srcs) {
		panic("internal error")
	}
	addrAttr := make([]ipAttr, len(addrs))
	srcAttr := make([]ipAttr, len(srcs))
	for i, v := range addrs {
		addrAttr[i] = ipAttrOf(v.IP)
		srcAttr[i] = ipAttrOf(srcs[i])
	}
	sort.Stable(&byRFC6724{
		addrs:    addrs,
		addrAttr: addrAttr,
		srcs:     srcs,
		srcAttr:  srcAttr,
	})
}

// srcsAddrs尝试通过UDP连接到每个地址，查看其是否有
// 路由。（这不会发送任何数据包）。目标端口
// 编号不相关。
func srcAddrs(addrs []IPAddr) []IP {
	srcs := make([]IP, len(addrs))
	dst := UDPAddr{Port: 9}
	for i := range addrs {
		dst.IP = addrs[i].IP
		dst.Zone = addrs[i].Zone
		c, err := DialUDP("udp", nil, &dst)
		if err == nil {
			if src, ok := c.LocalAddr().(*UDPAddr); ok {
				srcs[i] = src.IP
			}
			c.Close()
		}
	}
	return srcs
}

type ipAttr struct {
	Scope      scope
	Precedence uint8
	Label      uint8
}

func ipAttrOf(ip IP) ipAttr {
	if ip == nil {
		return ipAttr{}
	}
	match := rfc6724policyTable.Classify(ip)
	return ipAttr{
		Scope:      classifyScope(ip),
		Precedence: match.Precedence,
		Label:      match.Label,
	}
}

type byRFC6724 struct {
	addrs    []IPAddr // addrs排序
	addrAttr []ipAttr
	srcs     []IP // 如果无法访问
	srcAttr  []ipAttr
}

func (s *byRFC6724) Len() int { return len(s.addrs) }

func (s *byRFC6724) Swap(i, j int) {
	s.addrs[i], s.addrs[j] = s.addrs[j], s.addrs[i]
	s.srcs[i], s.srcs[j] = s.srcs[j], s.srcs[i]
	s.addrAttr[i], s.addrAttr[j] = s.addrAttr[j], s.addrAttr[i]
	s.srcAttr[i], s.srcAttr[j] = s.srcAttr[j], s.srcAttr[i]
}

// Less报告我是否比j.
// 
// 算法和变量名来自RFC 6724第6节。
func (s *byRFC6724) Less(i, j int) bool {
	DA := s.addrs[i].IP
	DB := s.addrs[j].IP
	SourceDA := s.srcs[i]
	SourceDB := s.srcs[j]
	attrDA := &s.addrAttr[i]
	attrDB := &s.addrAttr[j]
	attrSourceDA := &s.srcAttr[i]
	attrSourceDB := &s.srcAttr[j]

	const preferDA = true
	const preferDB = false

	// 规则1：避免无法使用的目的地。
	// 如果已知无法访问数据库，或者如果源（DB）未定义，则
	// 首选DA。类似地，如果已知DA不可访问，或者如果
	// 源（DA）未定义，则首选DB。
	if SourceDA == nil && SourceDB == nil {
		return false // “相等”
	}
	if SourceDB == nil {
		return preferDA
	}
	if SourceDA == nil {
		return preferDB
	}

	// 规则2：首选匹配范围。
	// 如果Scope（DA）=Scope（Source（DA））和Scope（DB）<>Scope（Source（DB）），则
	// 则首选DA。类似地，如果Scope（DA）<>Scope（Source（DA））和
	// Scope（DB）=Scope（Source（DB）），则首选DB。
	if attrDA.Scope == attrSourceDA.Scope && attrDB.Scope != attrSourceDB.Scope {
		return preferDA
	}
	if attrDA.Scope != attrSourceDA.Scope && attrDB.Scope == attrSourceDB.Scope {
		return preferDB
	}

	// 规则3：避免使用不推荐的地址。
	// 如果源（DA）已弃用，而源（DB）未弃用，则首选DB。
	// 类似地，如果源代码（DA）未被弃用，而源代码（DB）为
	// 弃用，则首选DA。

	// TODO（布拉德菲茨）：实施？目前优先级较低。

	// 规则4：首选家庭住址。
	// 如果源（DA）同时是家庭地址和转交地址
	// 而源（DB）不是，则首选DA。类似地，如果源（DB）是
	// 同时是家庭地址和转交地址，而源（DA）是
	// 则不是，则首选DB。

	// TODO（布拉德菲茨）：实施？目前优先级较低。

	// 规则5：首选匹配标签。
	// 如果Label（Source（DA））=Label（DA）和Label（Source（DB））<>Label（DB），则
	// 则首选DA。类似地，如果Label（Source（DA））<>Label（DA）和
	// Label（Source（DB））=Label（DB），则首选DB。
	if attrSourceDA.Label == attrDA.Label &&
		attrSourceDB.Label != attrDB.Label {
		return preferDA
	}
	if attrSourceDA.Label != attrDA.Label &&
		attrSourceDB.Label == attrDB.Label {
		return preferDB
	}

	// 规则6：优先选择更高的优先级。
	// 如果优先级（DA）>优先级（DB），那么选择DA。类似地，如果
	// 优先级（DA）<优先级（DB），则首选DB。
	if attrDA.Precedence > attrDB.Precedence {
		return preferDA
	}
	if attrDA.Precedence < attrDB.Precedence {
		return preferDB
	}

	// 规则7：更喜欢本机传输。
	// 如果DA是通过封装转换机制实现的（例如，
	// IPv4中的IPv6），而DB不是，则首选DB。类似地，如果DB是
	// 通过封装实现，而DA不是，则首选DA。

	// TODO（布拉德菲茨）：实施？目前优先级较低。

	// 规则8：选择较小的范围。
	// 如果范围（DA）<范围（DB），那么更喜欢DA。类似地，如果Scope（DA）>
	// Scope（DB），那么选择DB。
	if attrDA.Scope < attrDB.Scope {
		return preferDA
	}
	if attrDA.Scope > attrDB.Scope {
		return preferDB
	}

	// 规则9：使用最长匹配前缀。
	// 当DA和DB属于同一地址系列时（都是IPv6或
	// 都是IPv4[但见下文]）：如果CommonPrefixLen（源（DA），DA）>
	// CommonPrefixLen（源（DB），DB），则首选DA。类似地，如果
	// CommonPrefixLen（Source（DA），DA）<CommonPrefixLen（Source（DB），DB），则
	// 则首选DB。
	// 
	// 然而，将此规则应用于IPv4地址会导致
	// 问题（请参阅问题13283和18518），因此仅限于IPv6。
	if DA.To4() == nil && DB.To4() == nil {
		commonA := commonPrefixLen(SourceDA, DA)
		commonB := commonPrefixLen(SourceDB, DB)

		if commonA > commonB {
			return preferDA
		}
		if commonA < commonB {
			return preferDB
		}
	}

	// 规则10：否则，订单保持不变。
	// 如果在原始列表中DA在DB之前，则首选DA。
	// 否则，选择DB。
	return false // “相等”
}

type policyTableEntry struct {
	Prefix     *IPNet
	Precedence uint8
	Label      uint8
}

type policyTable []policyTableEntry

// /RFC 6724第2.1节。
var rfc6724policyTable = policyTable{
	{
		Prefix:     mustCIDR("::1/128"),
		Precedence: 50,
		Label:      0,
	},
	{
		Prefix:     mustCIDR("::/0"),
		Precedence: 40,
		Label:      1,
	},
	{
		// IPv4兼容等。
		Prefix:     mustCIDR("::ffff:0:0/96"),
		Precedence: 35,
		Label:      4,
	},
	{
		// 6to4 
		Prefix:     mustCIDR("2002::/16"),
		Precedence: 30,
		Label:      2,
	},
	{
		// Teredo 
		Prefix:     mustCIDR("2001::/32"),
		Precedence: 5,
		Label:      5,
	},
	{
		Prefix:     mustCIDR("fc00::/7"),
		Precedence: 3,
		Label:      13,
	},
	{
		Prefix:     mustCIDR("::/96"),
		Precedence: 1,
		Label:      3,
	},
	{
		Prefix:     mustCIDR("fec0::/10"),
		Precedence: 1,
		Label:      11,
	},
	{
		Prefix:     mustCIDR("3ffe::/16"),
		Precedence: 1,
		Label:      12,
	},
}

func init() {
	sort.Sort(sort.Reverse(byMaskLength(rfc6724policyTable)))
}

// 通过掩码长度按前缀大小对policyTableEntry进行排序。面具尺寸，
// 从最小的遮罩到最大的遮罩。
type byMaskLength []policyTableEntry

func (s byMaskLength) Len() int      { return len(s) }
func (s byMaskLength) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func (s byMaskLength) Less(i, j int) bool {
	isize, _ := s[i].Prefix.Mask.Size()
	jsize, _ := s[j].Prefix.Mask.Size()
	return isize < jsize
}

// mustCIDR调用ParseCIDR并对任何错误感到恐慌，或者如果网络
// 不是IPv6。
func mustCIDR(s string) *IPNet {
	ip, ipNet, err := ParseCIDR(s)
	if err != nil {
		panic(err.Error())
	}
	if len(ip) != IPv6len {
		panic("unexpected IP length")
	}
	return ipNet
}

// Classify返回包含ip的最长前缀匹配的条目的policyTableEntry。
// 表t必须从最大掩码大小到最小掩码大小排序。
func (t policyTable) Classify(ip IP) policyTableEntry {
	for _, ent := range t {
		if ent.Prefix.Contains(ip) {
			return ent
		}
	}
	return policyTableEntry{}
}

// RFC 6724第3.1节。
type scope uint8

const (
	scopeInterfaceLocal scope = 0x1
	scopeLinkLocal      scope = 0x2
	scopeAdminLocal     scope = 0x4
	scopeSiteLocal      scope = 0x5
	scopeOrgLocal       scope = 0x8
	scopeGlobal         scope = 0xe
)

func classifyScope(ip IP) scope {
	if ip.IsLoopback() || ip.IsLinkLocalUnicast() {
		return scopeLinkLocal
	}
	ipv6 := len(ip) == IPv6len && ip.To4() == nil
	if ipv6 && ip.IsMulticast() {
		return scope(ip[1] & 0xf)
	}
	// 站点本地地址在RFC 3513第2.5.6节
	// （在RFC 3879中已弃用）中定义。
	if ipv6 && ip[0] == 0xfe && ip[1]&0xc0 == 0xc0 {
		return scopeSiteLocal
	}
	return scopeGlobal
}

// commonPrefixLen报告
// 最重要或最左边的位），直到a的前缀的长度（即
// 两个地址共有的最长前缀的长度（看起来是
// 地址中不包括接口ID的部分）。
// 
// 如果a或b是作为IPv6地址的IPv4地址，则比较IPv4地址
// 的最大公共前缀长度为32。
// 如果a和b是不同的IP版本，则返回0。
// 参见https:
func commonPrefixLen(a, b IP) (cpl int) {
	if a4 := a.To4(); a4 != nil {
		a = a4
	}
	if b4 := b.To4(); b4 != nil {
		b = b4
	}
	if len(a) != len(b) {
		return 0
	}
	// 如果是IPv6，则仅限前缀（前64位）
	if len(a) > 8 {
		a = a[:8]
		b = b[:8]
	}
	for len(a) > 0 {
		if a[0] == b[0] {
			cpl += 8
			a = a[1:]
			b = b[1:]
			continue
		}
		bits := 8
		ab, bb := a[0], b[0]
		for {
			ab >>= 1
			bb >>= 1
			bits--
			if ab == bb {
				cpl += bits
				return
			}
		}
	}
	return
}
